import java.util.*;
import java.io.*;

/**
* Language
* Contains all necessary information for a LL(1) grammar
*/
public class Language{
	ArrayList tokens; // the potential terminal tokens
   ArrayList nonTerminals; // the possible nonterminals
   ArrayList start; // the start token
   Rule[] rules; // all the rules for the grammar
   ArrayList lines=new ArrayList(); // the lines of the input file
   ParsingTable parsingTable; // the parsing table for the language

   public Language(){
   	tokens=null;
      nonTerminals=null;
      start=null;
      rules=null;
	}

	/**
	* Constructor
	* pulls global variables from the given file
	* @param file 
	*/
   public Language(File file){
      setLines(file); // fill lines
      tokens=getInfo('T'); 
      nonTerminals=getInfo('N'); 
      start=getInfo('S');
      rules=getRules();
	  	removeLRec(); // removes left recursion
	  	removeLFact(); // removes left factoring
      parsingTable = new ParsingTable(start, tokens, nonTerminals, rules);
   }

	/**
	* prints a compact view of the language
	*/
   public void print(){
      String total="";
      total+="Tokens: ";
      for(int i=0;i<tokens.size();i++){
         total+=tokens.get(i);
         total+=" ";
      }
      total+="\nNonTerminals: ";
      for(int i=0;i<nonTerminals.size();i++){
         total+=nonTerminals.get(i);
         total+=" ";
      }
      total+="\nStart: ";
      for(int i=0;i<start.size();i++){
         total+=start.get(i);
         total+=" ";
      }
      total+="\nRules: \n";
      for(int i=0;i<rules.length;i++){
         total+=rules[i];
         total+="\n";
      }
      System.out.println(total);
   }
	
	/**
	* Prints the languages parsing table in list format
	*/
   public void printParsingTable(){
    	parsingTable.PrintTable();
   }
    
	/**
	* prints the languages parsing table in CSV format
	*/ 
   public void printTableCSV(){
    	parsingTable.PrintCSV();
    }
    
	/**
	* pulls each line from the input file and sets the global "lines"
	* @param file the input language file
	*/
   public void setLines(File file){
      BufferedReader reader = null;
   
      try {
         reader = new BufferedReader(new FileReader(file));
         String text = null;
      
      // repeat until all lines is read
         while ((text = reader.readLine()) != null) {
            lines.add(text); //add each line of text to the arraylist
         }
      } 
          catch (FileNotFoundException e) {
            System.out.println("NO FILE");
         } 
          catch (IOException e) {
            e.printStackTrace();
         } 
      finally {
         try {
            if (reader != null) {
               reader.close();
            }
         } 
             catch (IOException e) {
               e.printStackTrace();
            }
      }
   }

   public ArrayList getInfo(char c){
      int pos=0; //use characters to determine desired information
      if(c=='T'){ //tokens
         pos=0;
      }
      else if(c=='N'){ //nonterminals
         pos=1;
      }
      else if(c=='S'){ //start nonterminal
         pos=2;
      }
      String tokensS =(String)lines.get(pos); //get the line for information
      String[]	tokensA =tokensS.split("[ ]+"); //split into words
      ArrayList tokensL = new ArrayList();
      System.arraycopy((Object)tokensA,1,(Object)tokensA,0,tokensA.length-1); //remove the title of the line
      for(int i=0;i<tokensA.length-1;i++){
         tokensL.add(tokensA[i]); //add each word to the arraylist to return
      }
      return tokensL;
   }
	
	/**
	* Pulls the rules out of the lines global variable
	* @return an array of rule objects corresponding to the language
	*/
   public Rule[] getRules(){
      Rule[] rules = new Rule[lines.size()-4]; //ignore tokens, nonterminals, start, and rule title from file
      Rule rule;
		int tailCount=0;
      for(int i=4;i<lines.size();i++){
         rule = new Rule((String)lines.get(i));
         rules[i-4]=rule; //starting at 0 add each new rule to the array
      }
		for(int i=0;i<rules.length;i++){
			String[] tails = rules[i].getTail().split("[|]+");
			tailCount+=tails.length; // number of rules if each rule had it's own line with repetitive names
		}
		Rule[] full = new Rule[tailCount];
		int counter=0;
		for(int i=0;i<rules.length;i++){
			String[] tailsTemp = rules[i].getTail().split("[|]+"); //split each rule into individual rules
			for(int j=0;j<tailsTemp.length;j++){
				full[counter]=new Rule(); //create a new rule in each instance of the rules instructions
				full[counter].setHead(rules[i].getHead().trim()); //set the name of the rule the same for all instances
				full[counter].setTail(tailsTemp[j].trim()); //set the tail to each of the rules instructions
				counter++; //next rule
			}
		}
      return full; //return the rules with each on its own line
   }
	
	/**
	* Removes left recursion from the rules global
	*/
	public void removeLRec(){
	
		String tailS=null; //string version of the tail
		String[] tails=null; //string array of the words of the tail
		String headString=""; //the head of the rule as a string
		char[] headArray; //char array of the head
		char[] headTemp; //a temp used to modifiy the head of a rule
		Rule[] outTemp; //a temp used to extend the length of rules
		Rule rule = new Rule(); //the rule without the conflicting left recursion. the original becomes <rule'>
		
		for(int i=0;i<rules.length;i++){
			tailS=rules[i].getTail().split("[ ]+")[0]; //split the tail into words
			if(tailS.equals(rules[i].getHead())){ // if the first nonterminal is the same as the head then it's LR
				tails=rules[i].getTail().split("[ ]+");
				System.arraycopy((Object)tails,1,(Object)tails,0,tails.length-1); //shift everything left 1 removing LR
				headString=rules[i].getHead();
				headArray= new char[headString.length()+1];                              // turn the head into a Char array
				headTemp=rules[i].getHead().toCharArray();                               // that is then placed into 
				System.arraycopy((Object)headTemp,0,(Object)headArray,0,headTemp.length);// an array one char longer
				headArray[headString.length()-1]='\'';                                   // so you can add a ' symbol
				headArray[headString.length()]='>'; 
				headString = new String(headArray); // back to a string
				rules[i].setHead(headString); // and back into the rules head slot
				outTemp= new Rule[rules.length+1]; // create an array to include an empty set rule
				System.arraycopy((Object)rules,0,outTemp,0,rules.length); // same as rules
				rule = new Rule(); //except a new rule
				rule.setHead(headString); // with the same head as the LR rule w/ '
				rule.setTail("E"); // except the tail is the empty string
				outTemp[outTemp.length-1]=rule; // set the last rule to be this new one
				this.rules=outTemp; // replace the global
				tails[tails.length-1]=rules[i].getHead(); //Back to the LR rule, set the last word in the rule to the new head
				tailS=""; 
				for(int j=0;j<tails.length;j++){ //
					tailS+=tails[j]+" ";          // turn the tails array of strings into a string tailS
				}                                // that now has the ' title at the end
				tailS.trim();
				rules[i].setTail(tailS);         // set that to the new rule
				rules[i+1].setTail(rules[i+1].getTail()+" "+headString); //set the original rule to refer to the <rule'> version of itself
			}
		}
	}
	
	/**
	* Remove left factoring from the rules global
	*/
	public void removeLFact(){
	
		String tail=""; //rule's tail
		char[] tailc; //rule's tail as a char array
		char[] tailc2; //char array for manipulation
		Rule rule = new Rule(); //rule to manipulate
		Rule[] newRules = new Rule[rules.length]; //an array to eventually replace the global
		
		for(int i=0;i<rules.length;i++){      //
			for(int j=i+1;j<rules.length;j++){ //  only catch a repeat once... not in both directions
				//if the names are the same and the first nonterminals are the same, then it's Left Factoring
				if(rules[i].getHead().equals(rules[j].getHead())&&rules[i].getTail().split("[ ]+")[0].equals(rules[j].getTail().split("[ ]+")[0])){
					for(int k=1;k<rules[i].getTail().split("[ ]+").length;k++){
						tail+=rules[i].getTail().split("[ ]+")[k]+" "; //take everything except the first nonterminal
					}
					tail.trim(); 
					if(tail.equals("")){
						rules[i].setTail("E"); //if it was only a nonterminal it's now the empty set
					}
					else{
						rules[i].setTail(tail); //reset to the new tail
					}
					
					//repeat for for the other rule
					tail="";
					for(int k=1;k<rules[j].getTail().split("[ ]+").length;k++){
						tail+=rules[j].getTail().split("[ ]+")[k]+" ";
					}
					tail.trim();
					if(tail.equals("")){
						rules[j].setTail("E");
					}
					else{
						rules[j].setTail(tail);
					}
					//create a new rule
					rule.setHead(rules[i].getHead()); // same head
					tailc=rule.getHead().toCharArray(); //turn the head to a char array
					tailc2=new char[tailc.length+1]; //one char longer then the head
					System.arraycopy((Object)tailc,0,(Object)tailc2,0,tailc.length); //copy the head from the original
					tailc2[tailc2.length-2]='+'; //
					tailc2[tailc2.length-1]='>'; //insert a plus to show it's a different rule
					tail=new String(tailc2); // back to string
					rules[i].setHead(tail); // into the head of the rule
					rules[j].setHead(tail); // and into the other occurance as well
					rule.setTail(rule.getHead().toString()+" "+tail); // set the rule's tail to be the unaltered head plus the tail
					newRules= new Rule[newRules.length+1]; // newRules will contain this new rule 
					for(int k=0;k<rules.length;k++){ //same as rules for the most part
						newRules[k]=rules[k];
					}
					newRules[newRules.length-1]=rule; //just the one extra rule
					this.rules=newRules; //set global
				}
			}
		}
	}
}